package com.sanra;


public class ReverseListTest {
    public static void main(String[] args) {
        ListNode n5 = new ListNode(5, null);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);
//        ListNode prev = reverseList(n1);
        ListNode prev = recursionList(n1);
        System.out.println(prev);
    }

    static class ListNode {
        int value;
        ListNode next;

        public ListNode(int value, ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

    ///用两个变量分别保存当前节点的pre和next
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode next;
        ListNode curr = head;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;

            prev = curr;
            curr = next;
        }
        return prev;
    }

    //递归实现链表反转
    public static ListNode recursionList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curr = recursionList(head.next);
        head.next.next = head;
        head.next = null;
        return curr;
    }
}
